typedef int QDataType;
typedef struct QueueNode {
	QDataType x;
	struct QueueNode* next;
}Node;

typedef struct Queue
{
	Node* head;
	Node* tail;
	int size;
}Queue;

void QueueInit(Queue* ps);
void QueuePush(Queue* ps,QDataType x);
void QueuePop(Queue* ps);
bool QueueEmpty(Queue* ps);
QDataType QueueFront(Queue* ps);
QDataType QueueTail(Queue* ps);
int QueueSize(Queue* ps);
void QueueDestory(Queue* ps);

void QueueInit(Queue* ps)
{
	assert(ps);

	ps->head = ps->tail = NULL;
	ps->size = 0;
}

void QueuePush(Queue* ps, QDataType x)
{
	assert(ps);
	//创建新节点
	Node* newnode = (Node*)malloc(sizeof(Node));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->next = NULL;
	newnode->x = x;

	//尾插
	if (ps->tail == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = ps->tail->next;
	}
	ps->size++;
}

void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head);

	if (ps->head->next == NULL)
	{
		ps->head = ps->tail = NULL;
	}
	else
	{
		Node* next = ps->head->next;
		free(ps->head);
		ps->head = next;
	}
	
	ps->size--;
}

bool QueueEmpty(Queue* ps)
{
	assert(ps);

	return ps->tail == NULL;
}

QDataType QueueFront(Queue* ps)
{
	assert(ps);
	assert(ps->head);

	return ps->head->x;
}

QDataType QueueTail(Queue* ps)
{
	assert(ps);
	assert(ps->tail);

	return ps->tail->x;
}

int QueueSize(Queue* ps)
{
	assert(ps);
	return ps->size;
}

void QueueDestory(Queue* ps)
{
	assert(ps);

	Node* cur = ps->head;
	while (cur)
	{
		Node* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head=ps->tail = NULL;
    ps->size=0;
}

typedef struct {
    Queue queue1;
    Queue queue2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* mystack=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&mystack->queue1);
    QueueInit(&mystack->queue2);
    return mystack;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->queue1))
    {
        QueuePush(&obj->queue1,x);
    }
    else
    {
         QueuePush(&obj->queue2,x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* empty = &obj->queue1;
    Queue* nonempty=&obj->queue2;

    if(!QueueEmpty(&obj->queue1))
    {
        empty=&obj->queue2;
        nonempty=&obj->queue1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int top=QueueFront(nonempty);
    QueuePop(nonempty);
    return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->queue1))
    {
        return QueueTail(&obj->queue1);
    }
    else
    {
        return QueueTail(&obj->queue2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->queue1)&&QueueEmpty(&obj->queue2);
}

void myStackFree(MyStack* obj) {

    QueueDestory(&obj->queue1);
    QueueDestory(&obj->queue2);

    free(obj);
}